House robber III

Time: O(N); Space: O(H); medium

The thief has found himself a new place for his thievery again.

There is only one entrance to this area, called the “root.”

Besides the root, each house has one and only one parent house.

After a tour, the smart thief realized that “all houses in this place forms a binary tree”.

It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: root = {TreeNode} [3,2,3,None,3,None,1]

  3
 / \
2   3
 \   \
  3   1

Output: 7

Explanation:

  • Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = {TreeNode} [3,4,5,1,3,None,1]

    3
   / \
  4   5
 / \   \
1   3   1

Output: 9

Explanation:

  • Maximum amount of money the thief can rob = 4 + 5 = 9.

[2]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def robHelper(root):
            if not root:
                return (0, 0)
            left, right = robHelper(root.left), robHelper(root.right)
            return (root.val + left[1] + right[1], max(left) + max(right))

        return max(robHelper(root))

[4]:

s = Solution1()

root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)
assert s.rob(root) == 7

root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)
assert s.rob(root) == 9